import collections

class Solution:
    def numSubarraysWithSum1(self, nums, goal: int) -> int:
        cnt = 0
        sum_list = [0]
        for i, num in enumerate(nums):
            sum_list.append(sum_list[i] + num)
        begin = 0
        end = len(nums)
        while begin < len(nums):
            delta = sum_list[end] - sum_list[begin]

            if delta > goal:
                end -= 1
            elif delta == goal:
                cnt += 1
                end -= 1
            if end == begin or delta < goal:
                begin += 1
                end = len(nums)
        return cnt


    def numSubarraysWithSum1(self, nums, goal: int) -> int:
        cnt = 0
        sum_list = [0]
        for i, num in enumerate(nums):
            sum_list.append(sum_list[i] + num)
        begin = 0
        while begin < len(nums):
            cnt += sum_list[begin+1:].count(goal+sum_list[begin])
            begin += 1
        return cnt

    def numSubarraysWithSum(self, nums, goal) -> int:
        cnt = 0
        sum0 = 0
        pre_sum = Counter()
        for num in nums:
            pre_sum[sum0] += 1
            sum0 += num
            cnt += pre_sum[sum0 - goal]
        return cnt


nums = [0,0,0,0,0,0,1,0,0,0]
tester = Solution()
print(tester.numSubarraysWithSum(nums, 0))

